import java.util.HashSet;
import java.util.Set;

public class Solution433 {
    char[][] bankSet;

    char[] target;

    short len = 8;

    boolean[] path;

    char[] baseLib = new char[]{'A', 'G', 'C', 'T'};

    private void init(String[] bank){
        bankSet = new char[bank.length][len];
        for(short i = 0; i < bank.length; i++){
            bankSet[i] = bank[i].toCharArray();
        }
    }

    private boolean equals(char[] charArr1, char[] charArr2){
        for(short i = 0; i < len; i++){
            if(charArr1[i] != charArr2[i]){
                return false;
            }
        }
        return true;
    }

    private boolean canContinue(char[] charArr){
        for(short i = 0; i < bankSet.length; i++){
            char[] tmpCharArr = bankSet[i];
            if(equals(charArr, tmpCharArr) && !path[i]){
                path[i] = true;
                return true;
            }
        }
        return false;
    }

    private int dfs(char[] tmpCharArr, int step){
        if(equals(target, tmpCharArr)){
            return step;
        }
        int minMutation = Integer.MAX_VALUE;
        for(short i = 0; i < len; i++){
            char tmpChar = tmpCharArr[i];
            for(char base : baseLib){
                if(tmpChar == base){
                    continue;
                }
                tmpCharArr[i] = base;
                if(canContinue(tmpCharArr)){
                    minMutation = Math.min(dfs(tmpCharArr, step + 1), minMutation);
                }
                tmpCharArr[i] = tmpChar;
            }
        }
        return minMutation;
    }

    public int minMutation(String start, String end, String[] bank) {
        init(bank);
        target = end.toCharArray();
        path = new boolean[bank.length];
        int res = dfs(start.toCharArray(), 0);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public static void main(String[] args) {
        Solution433 s = new Solution433();
        System.out.println(s.minMutation("AACCGGTT", "AAACGGTA", new String[]{"AACCGGTA","AACCGCTA","AAACGGTA"}));
    }
}
